/*
Date:20210424 10:56pm
key:1.将2维压成1维，dp[i]为target为i的组合个数。
    那每一个组合到dp[i],无非就是通过加一个nums[0],nums[1]``nums[j]。
    因此就是dp[i]=累加dp[i-nums[j]], 注意要保证i-nums[j]>=0。
    2.答案保证了int，但是中间结果会有超过int的，那就结果mod int最大数即可，因为中间结果不可能要，否则加起来超过int。
*/

class Solution {
public:

    int combinationSum4(vector<int>& nums, int target) 
    {
        unsigned long long*dp=new unsigned long long[target+1];
        dp[0]=1;
        for(int i=1;i<target+1;i++)
        {
            dp[i]=0;
            for(int u:nums)
            {
                if(i-u>=0)
                {
                    dp[i]+=dp[i-u];
                }
            }
        }
        return dp[target];
    }
};